2307. Сумма

Дан массив из n элементов. Найти сумму чисел на отрезке.

Вход. Первая строка содержит два целых числа n и k (1 ≤ n ≤ 100000, 0 ≤ k ≤ 100000) – количество чисел в массиве и количество запросов. Следующие k строк содержат запросы двух видов:

· A l r x – присвоить элементам массива с позициями от l до r значение x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 10⁹)

· Q l r – найти сумму чисел в массиве на позициях от l до r (1 ≤ l ≤ r ≤ n)

Изначально в массиве находятся нули.

Выход. На каждый запрос вида “Q l r” следует вывести единственное число – сумму на отрезке.

Пример входа	Пример выхода
5 9 A 2 3 2 A 3 5 1 A 4 5 2 Q 1 3 Q 2 2 Q 3 4 Q 4 5 Q 5 5 Q 1 5	3 2 3 4 2 7

РЕШЕНИЕ

структуры данных – дерево отрезков

Анализ алгоритма

Для решения задачи следует реализовать дерево отрезков, поддерживающее групповую модификацию – присваивание и суммирование.

В каждом узле дерева в переменной add будем хранить значение, которое присвоено всем элементам отрезка, соответствующего этому узлу. Если вершина дерева соответствует отрезку [l; r], то сумма чисел на отрезке равна add * (r – l + 1). При дальнейших операциях присваивания и суммирования при движении по дереву от корня вниз значение add в каждой вершине следует проталкивать по дереву на один уровень ниже.

При операции присваивания предыдущие значения в сыновьях сумм s₁ и s₂, а также значения отложенных присавиваний a₁ и a₂ теряются.

При создании дерева инициализировать add в каждой вершине будем значением, которое никогда не будет присваиваться элементам отрезка (например -1).

Реализация алгоритма

Дерево отрезков храним в виде массива SegTree структур node длины MAX, где MAX – максимальное количество элементов, которое может храниться в отрезке.

#define MAX 100010

struct node

{

long long summa, add;

} SegTree[4*MAX];

Функция BuildTree строит дерево отрезков. Значение add в каждой вершине инициализируем -1 (значением, которое не может присваиваться элементам отрезка).

void BuildTree(int v, int lpos, int rpos)

{

Если вершине v соответствует отрезок, состоящий из одного элемента (lpos = rpos), то мы дошли до листа дерева отрезков. Изначально в массиве находятся нули, поэтому значению summa для текеущей вершины v присваиваем 0.

if (lpos == rpos)

{

SegTree[v].summa = 0;

SegTree[v].add = -1;

}

else

{

Находим середину отрезка mid = (lpos + rpos) / 2.

int mid = (lpos + rpos) / 2;

Разбиваем отрезок [left; right] на [left; mid] и [mid + 1; right]. Запускаем рекурсивно построение дерева отрезков на подотрезках.

BuildTree(2*v, lpos, mid);

BuildTree(2*v+1, mid + 1, rpos);

Пересчитываем значение суммы в текущей вершине дерева отрезков. Проталкивать в текущей вершине изначально нечего, поэтому установим add = -1.

SegTree[v].summa = SegTree[2*v].summa + SegTree[2*v+1].summa;

SegTree[v].add = -1;

}

}

Функция Push производит проталкивание значения add вершины v в сыновья. Если add ≠ -1, то его следует протолкнуть на один уровень вниз. После проталкивания значение add в вершине v ставим равным -1.

void Push(int v, int lpos, int mid, int rpos)

{

Если add = -1, то отложенной операции в вершине v нет.

if (SegTree[v].add == -1) return;

Совершаем пересчет значений add и summa в сыновьях вершины v.

SegTree[2*v].add = SegTree[v].add;

SegTree[2*v].summa = (mid - lpos + 1) * SegTree[v].add;

SegTree[2*v+1].add = SegTree[v].add;

SegTree[2*v+1].summa = (rpos - mid) * SegTree[v].add;

Проталкивание завершено. Установим add = -1.

SegTree[v].add = -1;

}

Функция SetValue устанавливает все элементы отрезка [left; right] равными val. Вершине v соответствует отрезок [lpos; rpos].

void SetValue(int v, int lpos, int rpos, int left, int right, int val)

{

if (left > right) return;

Если [left; right] соответствует отрезку, который хранится в вершине дерева [lpos; rpos], то присваиваем в текущей вершине дерева переменным add и summa соответствующие значения.

if ((lpos == left) && (rpos == right))

{

SegTree[v].add = val;

SegTree[v].summa = (long long)(right - left + 1) * val;

return;

}

Находим середину отрезка mid = (lpos + rpos) / 2.

int mid = (lpos + rpos) / 2;

Проведем проталкивание, если add не равно -1.

Push(v, lpos, mid, rpos);

Рекурсивно обрабатываем левого и правого сына текущей вершины дерева отрезков.

SetValue(2*v, lpos, mid, left, min(mid, right), val);

SetValue(2*v+1, mid+1, rpos, max(left, mid+1), right, val);

Пересчитываем значение суммы в вершине v через значения сумм ее детей.

SegTree[v].summa = SegTree[2*v].summa + SegTree[2*v+1].summa;

}

Функция Summa возвращает значение суммы на отрезке [left; right].

Вершине v соответствует отрезок [lpos; rpos].

long long Summa(int v, int lpos, int rpos, int left, int right)

{

if (left > right) return 0;

Если [left; right] совпадает с отрезком [lpos; rpos], который хранится в вершине v дерева, то возвращаем находящееся в ней значение суммы.

if ((lpos == left) && (rpos == right))

return SegTree[v].summa;

Находим середину отрезка mid = (lpos + rpos) / 2.

int mid = (lpos + rpos) / 2;

Проведем проталкивание, если add не равно -1.

Push(v, lpos, mid, rpos);

Разбиваем отрезок [lpos; rpos] на [lpos; mid] и [mid + 1; rpos]. Запускаем рекурсивно вычисление сумм на подотрезках. Складываем полученные суммы.

return Summa(2*v, lpos, mid, left, min(mid, right)) +

Summa(2*v+1, mid+1, rpos, max(left, mid+1), right);

}

Основная часть программы. При помощи функции BuildTree строим дерево отрезков.

scanf("%d %d\n",&n,&k);

build(1,1,n);

Обрабатываем k запросов. В зависимости от входного запроса совершаем либо групповое присваивание, либо вычисление суммы на отрезке.

while(k--)

{

scanf("%c ",&c);

if (c == 'A')

{

scanf("%d %d %d\n",&l,&r,&x);

SetValue(1,1,n,l,r,x);

}

else

{

scanf("%d %d\n",&l,&r);

printf("%lld\n",Summa(1,1,n,l,r));

}

}

Реализация с помощью класса

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class SegmentTree

{

public:

const static int NONE_ASSIGN = -1;

vector<long long> Summa, Add;

int len;

SegmentTree(int n)

{

len = n;

Summa.resize(4*n);

Add.resize(4* n);

BuildZeroTree(1, 1, len);

}

void BuildZeroTree(int v, int lpos, int rpos)

{

if (lpos == rpos)

{

Summa[v] = 0;

Add[v] = NONE_ASSIGN;

}

else

{

int mid = (lpos + rpos) / 2;

BuildZeroTree(2*v, lpos, mid);

BuildZeroTree(2*v+1, mid + 1, rpos);

Summa[v] = Summa[2*v] + Summa[2*v+1];

Add[v] = NONE_ASSIGN;

}

}

void Push(int v, int lpos, int mid, int rpos)

{

if (Add[v] == NONE_ASSIGN) return;

Add[2*v] = Add[v];

Summa[2*v] = (mid - lpos + 1) * Add[v];

Add[2*v+1] = Add[v];

Summa[2*v+1] = (rpos - mid) * Add[v];

Add[v] = NONE_ASSIGN;

}

void SetValue(int left, int right, int val)

{

SetValue(1, 1, len, left, right, val);

}

void SetValue(int v, int lpos, int rpos,

int left, int right, int val)

{

if (left > right) return;

if ((lpos == left) && (rpos == right))

{

Add[v] = val;

Summa[v] = (long long)(right - left + 1) * val;

return;

}

int mid = (lpos + rpos) / 2;

Push(v, lpos, mid, rpos);

SetValue(2*v, lpos, mid, left, min(mid, right), val);

SetValue(2*v+1, mid+1, rpos, max(left, mid + 1), right, val);

Summa[v] = Summa[2*v] + Summa[2*v+1];

}

long long Sum(int left, int right)

{

return Sum(1, 1, len, left, right);

}

long long Sum(int v, int lpos, int rpos, int left, int right)

{

if (left > right) return 0;

if ((lpos == left) && (rpos == right)) return Summa[v];

int mid = (lpos + rpos) / 2;

Push(v, lpos, mid, rpos);

return Sum(2*v, lpos, mid, left, min(mid, right)) +

Sum(2*v+1, mid+1, rpos, max(left, mid + 1), right);

}

};

int n, k, l, r, x;

char c;

int main(void)

{

scanf("%d %d\n", &n, &k);

SegmentTree s(n);

while (k--)

{

scanf("%c ", &c);

if (c == 'A')

{

scanf("%d %d %d\n", &l, &r, &x);

s.SetValue(l, r, x);

}

else

{

scanf("%d %d\n", &l, &r);

printf("%lld\n", s.Sum(l, r));

}

}

return 0;

}

Реализация дерева отрезков на указателях

Из элементов вектора v функция build создает дерево отрезков.

SegmentTree *build(vector<long long> &v, int L, int R)

{

if (L == R)

{

SegmentTree *New = new SegmentTree ;

New->summa = v[L]; New->add = -1;

New->Left = New->Right = NULL;

New->LeftPos = New->RightPos = L;

return New;

}

int m = (L + R) / 2;

SegmentTree *Left = build(v,L,m);

SegmentTree *Right = build(v,m+1,R);

SegmentTree *Tree = new SegmentTree;

Tree->Left = Left; Tree->Right = Right;

Tree->summa = Left->summa + Right->summa;

Tree->LeftPos = Left->LeftPos;

Tree->RightPos = Right->RightPos;

Tree->add = -1;

return Tree;

}

Функция SetValue присваивает значение value всем элементам на отрезке [L; R].

void SetValue(SegmentTree *&tree, int L, int R, long long value)

{

if (L < tree->LeftPos) L = tree->LeftPos;

if (R > tree->RightPos) R = tree->RightPos;

if (L > R) return;

Если [L; R] соответствует отрезку, который хранится в вершине дерева [LeftPos; RightPos], то присваиваем в текущей вершине дерева переменным add и summa соответствующие значения.

if ((tree->LeftPos == L) && (tree->RightPos == R))

{

tree->add = value;

tree->summa = value * (R - L + 1);

return;

}

Если значение tree->add установлено (не равно -1), то следует протолкнуть его на уровень ниже. При этом следует пересчитать значение суммы в дочерних вершинах tree->Left->summa и tree->Right->summa.

if (tree->add != -1)

{

if (tree->Left != NULL)

tree->Left->add = tree->add,

tree->Left->summa = tree->add *

(tree->Left->RightPos - tree->Left->LeftPos + 1);

if (tree->Right != NULL)

tree->Right->add = tree->add,

tree->Right->summa = tree->add *

(tree->Right->RightPos - tree->Right->LeftPos + 1);

tree->add = -1;

}

Рекурсивно модифицируем левое и правое поддерево. Пересчитываем значение суммы в текущей вершине дерева.

SetValue(tree->Left,L,R,value);

SetValue(tree->Right,L,R,value);

tree->summa = tree->Left->summa + tree->Right->summa;

}

Функция Summa возвращает значение суммы на отрезке [L; R].

long long Summa(SegmentTree *&tree, int L, int R)

{

if (L < tree->LeftPos) L = tree->LeftPos;

if (R > tree->RightPos) R = tree->RightPos;

if (L > R) return 0;

Если [L; R] соответствует отрезку в вершине дерева, то возвращаем хранящееся в нем значение суммы.

if ((tree->LeftPos == L) && (tree->RightPos == R))

return tree->summa;

Производим проталкивание значения add на уровень ниже с пересчетом суммы для дочерних узлов.

if (tree->add != -1)

{

if (tree->Left != NULL)

tree->Left->add = tree->add,

tree->Left->summa = tree->add *

(tree->Left->RightPos - tree->Left->LeftPos + 1);

if (tree->Right != NULL)

tree->Right->add = tree->add,

tree->Right->summa = tree->add *

(tree->Right->RightPos - tree->Right->LeftPos + 1);

tree->add = -1;

}

Возвращаем искомую сумму, извлекая информацию из левого и правого поддерева.

return Summa(tree->Left,L,R) + Summa(tree->Right,L,R);

}

Основная часть программы. Строим дерево отрезков Tree, содержащее изначально все нули. В зависимости от входного запроса совершаем либо групповое присваивание, либо вычисление суммы на отрезке.

scanf("%d %d\n",&n,&k);

Tree = build(v,0,n);

while(k--)

{

scanf("%c ",&c);

if (c == 'A')

{

scanf("%d %d %d\n",&l,&r,&x);

SetValue(Tree,l,r,x);

}

else

{

scanf("%d %d\n",&l,&r);

printf("%lld\n",Summa(Tree,l,r));

}

}